package jianzhioffer;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/22 16:19
 * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 */
public class offer_45_把数组排成最小的数 {

    public static void main(String[] args) {
//        int[] nums = {10, 2};
        int[] nums = {3, 30, 34, 5, 9};
        System.out.println(minNumber(nums));
    }

//    先排序，然后拼接
    public static String minNumber1(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i=0; i<nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        quickSort(strs, 0, strs.length-1);
        System.out.println(Arrays.toString(strs));
        String re = "";
        for (int k=0; k<strs.length; k++){
            re += strs[k];
        }
        System.out.println(re);
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }

    public static void quickSort(String[] strs, int l, int r){
        if (l>=r) return;
        int i=l, j=r;
        while (i<j){
            while ((strs[j]+strs[l]).compareTo(strs[l]+strs[j]) >= 0 && i < j) j--;
            while ((strs[i]+strs[l]).compareTo(strs[l]+strs[i]) <= 0 && i < j) i++;
            swap(strs, i, j);
        }
        swap(strs, i, l);
        quickSort(strs, l, i-1);
        quickSort(strs, i+1, r);
    }

    public static void swap(String[] strs, int i, int j){
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }

//    使用内置函数
    public static String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i=0; i<nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);
        return res.toString();
    }
}
